\documentclass[preprint,11pt]{elsarticle}
%\usepackage{numcompress}
%
\usepackage{algcompatible}
\usepackage{algorithm}
%\usepackage{algorithmic}
%\usepackage{caption}

\usepackage{graphics}
\usepackage{graphicx}
\usepackage{epsfig}
 
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{fullpage}
%\biboptions{comma,round}
 
\journal{Journal of Parallel and Distributed Computing}

\newtheorem{theorem}{Theorem}[section]
%\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
%\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
\theoremstyle{observation}\newtheorem{observation}[theorem]{Observation}


\newcommand{\comment}[1]{}
%\newcommand{\QED}{\mbox{}\hfill \rule{3pt}{8pt}\vspace{10pt}\par}
%\newcommand{\eqref}[1]{(\ref{#1})}
\newcommand{\theoremref}[1]{(\ref{#1})}
%\newenvironment{proof1}{\noindent \mbox{}{\bf Proof:}}{\QED}
%\newenvironment{observation}{\mbox{}\\[-10pt]{\sc Observation.} }%
%{\mbox{}\\[5pt]}


\def\m{{\rm min}}
%\def\m{\bar{m}}
\def\eps{{\epsilon}}
\def\half{{1\over 2}}
\def\third{{1\over 3}}
\def\quarter{{1\over 4}}
\def\polylog{\operatorname{polylog}}
\newcommand{\ignore}[1]{}
\newcommand{\eat}[1]{}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

\newcommand{\algorithmsize}[0]{}

%---------------------
%  SPACE SAVERS
%---------------------

%\usepackage{times}
%\usepackage[small,compact]{titlesec}
%\usepackage[small,it]{caption}

\newcommand{\squishlist}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{3pt}
     \setlength{\topsep}{3pt}
     \setlength{\partopsep}{0pt}
     \setlength{\leftmargin}{1.5em}
     \setlength{\labelwidth}{1em}
     \setlength{\labelsep}{0.5em} } }
\newcommand{\squishend}{
  \end{list}  }

%---------------------------------
% FOR MOVING PROOFS TO APPENDIX
%\usepackage{answers}
%%\usepackage[nosolutionfiles]{answers}
%\Newassociation{movedProof}{MovedProof}{movedProofs}
%\renewenvironment{MovedProof}[1]{\begin{proof}}{\end{proof}}

\def\e{{\rm E}}
\def\var{{\rm Var}}
\def\ent{{\rm Ent}}
\def\eps{{\epsilon}}
\def\lam{{\lambda}}
\def\bone{{\bf 1}}




\begin{document}

\begin{frontmatter}

\title{Efficient Random Walk Sampling in Distributed Networks\tnoteref{t1}}
\tnotetext[t1]{A short version of the paper appeared in the Proceedings of 31st Annual IEEE International Conference on Computer Communications (IEEE INFOCOM), 2012, pages 2906-2910, \cite{infocom12}.}


\author[atish]{Atish {Das Sarma}}
\ead{atish.dassarma@gmail.com}

\author[anisur]{Anisur Rahaman Molla}
\ead{anisurpm@gmail.com}

\author[gopal]{Gopal Pandurangan\corref{cor}}
\ead{gopalpandurangan@gmail.com}

%
\cortext[cor]{Supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, Singapore MOE  AcRF Tier 1 grant MOE2012-T1-001-094, and a grant from the US-Israel Binational Science Foundation (BSF).}

%


\address[atish]{eBay Research Labs, eBay Inc., CA, USA.}
\address[anisur]{Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371.}
\address[gopal]{Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 and Department of Computer Science, Brown University, Providence, RI 02912, USA.}




%First definitions. Use these when you want to read comments.
%\def\prasad#1{\marginpar{$\leftarrow$\fbox{P}}\footnote{$\Rightarrow$~{\sf #1 --Prasad}}}
\def\anisur#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 --Anisur}}}
%\def\gopal#1{\marginpar{$\leftarrow$\fbox{G}}\footnote{$\Rightarrow$~{\sf #1 --Gopal}}}
%\def\atish#1{\marginpar{$\leftarrow$\fbox{A}}\footnote{$\Rightarrow$~{\sf #1 --Atish}}}
%
%Second definitions. Use these to remove all comments.
\def\anisur#1{}
%\def\danupon#1{}
\def\gopal#1{}
\def\atish#1{}

\begin{abstract}

Performing random walks in networks is a fundamental primitive that has found  numerous applications in communication networks such as token management, load balancing, network topology discovery and construction,  search, and peer-to-peer membership management. While several such algorithms are ubiquitous, and use numerous random walk samples, the walks themselves have always been performed naively. 

In this paper, we focus on the problem of performing random walk sampling efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds and messages required to obtain several random walk samples in a continuous online fashion. We present the first round and message optimal distributed algorithms that present a significant improvement on all previous approaches. The theoretical analysis and comprehensive simulations of our algorithms show that they perform very well in different types of networks of differing topologies. 

In particular, our results show how several random walks can be performed continuously (when source nodes are provided only at runtime, i.e., online), such that each walk of length $\ell$ can be performed exactly in just $\tilde{O}(\sqrt{\ell D})$ rounds\footnote{Throughout this paper, $\tilde{O}$ hides polylogarithmic factors in the number of nodes in the network.} (where $D$ is the diameter of the network), and $O(\ell)$ messages. This significantly improves upon both, the naive technique that requires $O(\ell)$ rounds and $O(\ell)$ messages, and the sophisticated algorithm of \cite{drw-jacm} that has the same round complexity as this paper but requires $\Omega(m\sqrt{\ell})$ messages (where $m$ is the number of edges in the network). Our theoretical results are corroborated through extensive simulations on various topological data sets. Our algorithms are fully decentralized, lightweight, and easily implementable, and can serve as building blocks in the design of topologically-aware networks.

\end{abstract}

\begin{keyword}
Random walks; Random sampling; Decentralized computation; Distributed algorithms; Self-aware network 

\end{keyword}

\end{frontmatter}


\input{introduction}

\input{TheoreticalAnalysis}

\input{concentrationanalysis}

\input{experiments}

\input{conclusion}

%\newpage
\bibliographystyle{abbrv}
%\bibliographystyle{plain}
\bibliography{Distributed-RW}

%\input{authorInfo}

%\newpage
%\section*{Appendix}
%\appendix
%\input{appendix1}

\end{document}
